package leetcode

import kotlinetc.println

/**
Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
 */

fun main(args: Array<String>) {

    val intervals = arrayOf(
            intArrayOf(1, 4),
            intArrayOf(2, 6),
            intArrayOf(8, 10),
            intArrayOf(15, 18)
    )


    val interval1 = arrayOf(
            intArrayOf(2, 3),
            intArrayOf(4, 5),
            intArrayOf(6, 7),
            intArrayOf(8, 9),
            intArrayOf(1, 10)
    )

    val interval2 = arrayOf(
            intArrayOf(1, 4),
            intArrayOf(3, 5),
            intArrayOf(0, 2)
    )

//    interval1.sortBy { it[0] }
//    interval1.forEach { it.asList().println() }

    merge(interval2).forEach {
        it.asList().println()
    }
}

/**
 * 合并有交集的区间,按照每个区间的左边界大小排序，然后以第一个区间作为基准区间，让后面的区间
 * 和基准区间比较，如果可以合并则合并产生新区间并作为新的基准区间。直到不能合并为止，选定新的基准区间
 */
fun merge(intervals: Array<IntArray>): Array<IntArray> {

    if (intervals.size <= 1) return intervals

    intervals.sortBy { it[0] }

    val result = arrayListOf<IntArray>()

    var baseStart = intervals[0][0]
    var baseEnd = intervals[0][1]



    var k = 1
    while (k < intervals.size) {
        val arr = intervals[k]
        if (arr[0] <= baseEnd) {  //intersect
            baseEnd = Math.max(baseEnd, arr[1])

        } else {
            //add the already merged interval
            result.add(intArrayOf(baseStart, baseEnd))

            //set a new base interval for further judging
            baseStart = arr[0]
            baseEnd = arr[1]
        }

        if (k == intervals.size - 1)
            result.add(intArrayOf(baseStart, baseEnd))
        k++
    }

    return result.toTypedArray()
}